
from DoubleLinkedList import DoubleLinkedList, Node


class LRUCache():

    def __init__(self, capacity):
        self.capacity = capacity
        self.map = {}
        self.list = DoubleLinkedList(self.capacity)
        self.size = 0

    def get(self, key):
        """
            LRU算法，当在链表中时，不仅缓存，还要将缓存置于链表头部
        """
        node = self.map.get(key, None)

        if not node: return -1
        self.list.remove(node)
        self.list.append_front(node)
        return node.value


    def put(self, key, value):
        """
            if 已经存在该结点：
                （实际上就是更新cache了）
                1. 删除原来在的位置
                2. 更新值value
                3. 重新插入到链表头部
            else: 
                if 缓存已经满了（达到长度）
                    删除最后一个元素（最近最少使用的结点）
                    表头加入新元素
                else:
                    未满，直接表头加元素
        """
        node = self.map.get(key, None)

        if node:
            self.list.remove(node)
            node.value = value
            self.list.append_front(node)
        else:
            node = Node(key, value)
            if self.size == self.capacity:
                old_node = self.list.remove()
                self.map.pop(old_node.key)
                self.size -= 1

            self.list.append_front(node)
            self.map[key] = node
            self.size += 1

    
    def print(self):
        self.list.print()


# 测试
if __name__ == '__main__':
    cache = LRUCache(2)
    cache.put(2, 2)
    cache.print()
    cache.put(1, 1)
    cache.print()
    cache.put(3, 3)
    cache.print()
    print(cache.get(1))
    cache.print()
    print(cache.get(2))
    cache.print()
    print(cache.get(3))
    cache.print()


